import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;


class test {
	public static int compute(int steps,int n) {
		
		if(steps<1 || n==0) {
			return 0;
		}else if (steps==1) {
			return 1;
		}else if(steps==2) {
			return 2;
		}else {
			int s = compute(steps-1, n-1)+compute(steps-1, n);
			return s ;
		}
	}
	
	
	public static BigInteger compute2(int steps) {
		int steps_2 = steps / 2;
		BigInteger result = BigInteger.ZERO;
		for (int i = 0; i <= steps_2; i++) {
			int steps_1 = steps - 2 * i;
			int steps_all = steps_1 + i;
			BigInteger counts = jiecheng(steps_all)
					.divide(jiecheng(i).multiply(jiecheng(steps_1)));
			// System.out.println("step_2:" + i + ",counts:" + counts);
			result = result.add(counts);
		}

		return result;
	}

	public static BigInteger jiecheng(int n) {
		if (n <= 0) {
			return BigInteger.ONE;
		}
		BigInteger result = BigInteger.ONE;
		for (long i = 1; i <= n; i++) {
			result = result.multiply(BigInteger.valueOf(i));
		}
		return result;
	}
	
	@SuppressWarnings("null")
	public static Double FoundMiddleNum(int[] aArray,int[] bArray) {
		List<Integer> cList = new ArrayList<>();
		int t=0;
		for(int i=0;i<aArray.length;i++) {
			for(int j=t;j<bArray.length;j++) {
				if(aArray[i]<bArray[j]) {
					int a=aArray[i];
					cList.add(a);
					t=j;
					break;
				}else {
					cList.add(bArray[j]);
				}
				
			}
		}
		int aLen=aArray.length;
		int bLen=bArray.length;
		if(aLen>bLen) {
			for(int i=bLen;i<aLen;i++) {
				cList.add(aArray[i]);
			}
		}else {
			for(int i=aLen;i<bLen;i++) {
				cList.add(bArray[i]);
			}
		}
		
		
		System.out.println(cList);
		int pos=cList.size()/2;
		if(cList.size()%2==0) {
			return ((double)cList.get(pos)+cList.get(pos-1))/2;
		}
		else {
			return (double)cList.get(pos);
		}
		
	}
	
	
	
	public static void main(String[] args) {
		int[] aArray= {1,4,9,12};
		int[] bArray= {2,3,10,15};
		System.out.println(FoundMiddleNum(aArray, bArray));
	}
}